/*-------------------------------------------------------------------------*/
/**
  @file		plotlib_graph.c
  @author	Renaud Wanschoor
  @date	july 2004
  @version	$Revision: 2.5 $
  @brief	contains plib functions that are specific to a grid

  plib functions are used to serialize matchings sequences and results of each
  level of the uncoarsening stage. They are currently used for METIS and PaGrid
  pagridplot also used plib functions.

  there are also utilities used by pagrid in plib, those are error handling,
  memory allocation, priority queues, randum number generator, dll as macros
  io functions, in fact all utils that may used for other programs.

  This files contains functions for ::PlotGridType management
  
*/
/*--------------------------------------------------------------------------*/
#include "plib.h"

void* PLIBN_Init(void){
  PlotGridType *g;

  g = U_malloc(1,PlotGridType,"PLIBN_Init error code 1\n");

  g->npro = g->nedges = g->r_from = g->r_to = 0;
  g->r_val = 0;
  g->ratio = NULL;
  g->exec  = NULL;
  g->netcost = NULL;
  g->penalty = NULL;
  g->proratio = g->proportion = g->prospeed = NULL;

  MEM_Init(&(g->mem));

  return g;

}

void PLIBN_Free(PlotGridType *grid){
  if(grid!=NULL){
    MEM_Free(&(grid->mem));
    U_free("PLIBN_Free error code 1\n",&grid,LEND);
  }
}


double PLIBN_RatioRef(PlotGridType *g,double ratio){
  if(ratio <= 0)
    ratio = g->r_val;
  
  return ratio * g->prospeed[g->r_from] / g->netcost[g->r_from][g->r_to];
}


PlotGridType* PLIBN_Read(FILE* fp){
  int i,j,k;
  int dist;

  char line[MAXLINE];
  char *tok1,*tok2;
  int linenb = 1;
  
  PlotGridType* g;
  
  int npro = 0;
  int nedges = 0;  			
  int **netcost;
  double **ratio,*proportion;
  double *prospeed;
  int maxproportion = 0;
  int *sadjidx,*sadjncy,*sadjwgt,*adjidx,*adjncy,*adjwgt;
  Mem *mem;

  /* reference ratio readen from file */
  int r_from,r_to;
  double r_val;
  double r_ref;  
  
  g = PLIBN_Init();
  mem = &(g->mem);
  
  /******************************************/
  /* read two first lines                   */
  /******************************************/
  /* read first line (number of processors and edges number) */
  do { 
    fgets(line, MAXLINE, fp);
    linenb++;
  } while (line[0] == '%' && !feof(fp));
  WARNING((sscanf(line,"%d %d",&npro,&nedges) != 2,
	   "GD_PagridReadGrid error code 1 : cannot read the number of processors and number of links, line %d\n",
	   linenb),
	  NULL);
  g->nedges = nedges = nedges*2;

  /* read second line (application ratio) */
  do { 
    fgets(line, MAXLINE, fp);
    linenb++;
  } while (line[0] == '%' && !feof(fp));
  WARNING((sscanf(line,"%d %d %lf",&r_from,&r_to,&r_val) != 3,
	   "GD_PagridReadGrid error code 2 : cannot read application ratio line %d\n",linenb),
	  NULL);

  /*****************************************/
  /* Init                                  */
  /*****************************************/
  g->npro = npro;
  
  MEM_Needxy(mem, npro, npro,        int   );
  MEM_Needxy(mem, npro, npro,        double);
  MEM_Need  (mem, 3*npro,            double);  
  MEM_Need  (mem, npro,              int);

  MEM_Allocate(mem);
    
  netcost     = g->netcost     = MEM_Requestxy(mem, npro, npro, int   );  
  proportion  = g->proportion  = MEM_Request  (mem, npro,       double);
  prospeed    = g->prospeed    = MEM_Request  (mem, npro,       double);
  ratio       = g->ratio       = MEM_Requestxy(mem, npro, npro, double);  

  g->penalty                   = MEM_Request  (mem, npro,       int);
  g->exec                      = MEM_Request  (mem, npro,       double);
  
  sadjidx = adjidx = U_malloc(npro+1,int,"PLIBN_Read malloc error\n");
  sadjncy = adjncy = U_malloc(nedges,int,"PLIBN_Read malloc error\n");
  sadjwgt = adjwgt = U_malloc(nedges,int,"PLIBN_Read malloc error\n");

  *adjidx = 0;
  for(i=0;i<npro;i++)
    g->exec[i] = 0;

  /*************/
  /* read file */
  /*************/
  for(i=0;i<npro;i++){
    do { 
      fgets(line, MAXLINE, fp);
      linenb++;
    } while (line[0] == '%' && !feof(fp));
    WARNING((strlen(line) >= MAXLINE,
	     "GD_PagridReadGrid error code 11 : line too long, line %d\n",
	     linenb),
	    NULL);

    /* proportion */
    WARNING(((tok1 = strtok(line," ")) == NULL,
	     "GD_PagridReadGrid error code 12 : cannot read processor proportion, line %d\n",
	     linenb),
	    NULL);
    proportion[i] = atoi(tok1);
    if(proportion[i] > maxproportion)
      maxproportion = proportion[i];
    
    /* connectivity  matrix */
    j = *(adjidx++);
    *adjidx = j;

    while((tok1 = strtok(NULL," ")) != NULL && (tok2 = strtok(NULL," ")) != NULL){
      j = atoi(tok1);
      dist = atoi(tok2);

      (*adjidx)++;
      *(adjncy++) = j;
      *(adjwgt++) = dist;
    }
  }

  /* scale proportion to have fastest processor proportion = 1 */
  for(i=0;i<npro;i++){
    proportion[i] /= maxproportion;
    prospeed[i]   =  1/proportion[i];
  }

  adjidx    = sadjidx;
  adjncy    = sadjncy;
  adjwgt    = sadjwgt;
  

  /************************/
  /* generate realnetcost */
  /************************/
  /* dantzig algo for all to all shortest paths */
  /* init */
  for(i=0; i<npro;i++)
    for(j=0; j<npro; j++) 
      netcost[i][j]=(i==j? 0 : INFINITY);

  /* rock and roll */
  for( k=0; k<npro; k++){
    for(i=0; i<k; i++) /* compute D[i][k] = D[k][i] */{
      dist = INFINITY;

      for( j=adjidx[k];j<adjidx[k+1];j++){
	if(adjncy[j] >= k)
	  continue;
	if ( netcost[i][adjncy[j]]+adjwgt[j] < dist) 
	  dist=netcost[i][adjncy[j]]+adjwgt[j];
      }
      if( dist!=INFINITY) 
	netcost[i][k] = netcost[k][i] = dist;
    }
    for(i=0; i<k; i++) for( j=0; j<k; j++)
      if ( netcost[i][k] + netcost[k][j] < netcost[i][j])
	netcost[i][j] = netcost[i][k] + netcost[k][j];
  }
    
  /*************************/
  /* generate ratio matrix */
  /*************************/
  g->r_from = r_from;
  g->r_to   = r_to;
  g->r_val  = r_val;
  r_ref = r_val * prospeed[r_from] / netcost[r_from][r_to];
  //r_ref = r_val / (proportion[r_from] * netcost[r_from][r_to]);
  for(i=0;i<npro;i++)for(j=0;j<npro;j++){
    //ratio[i][j] = r_ref * netcost[i][j] / prospeed[i];
    ratio[i][j] = r_ref * netcost[i][j];
    //ratio[i][j] = r_ref * netcost[i][j] * proportion[i];
  }
  
  /**********************/
  /*  debug             */
  /**********************/
#ifdef DEBUGEXEC
  /*printf("netcost\n");
  for(i=0;i<npro;i++){
    for(j=0;j<npro;j++)
      printf(" %5d",netcost[i][j]);
    printf("\n");
  }
  printf("\nratio\n");
  for(i=0;i<npro;i++){
    for(j=0;j<npro;j++)
      printf(" %5.2f",ratio[i][j]);
    printf("\n");
  }

  printf("\n Final Proceesor Graph\n");
  for (i=0; i<npro; i++){
    printf (" processor %d (%f) connects to : ", i, proportion[i]);
    for (j=adjidx[i]; j<adjidx[i+1]; j++)
      printf(" %2d (%2d)", adjncy[j],adjwgt[j]);
    printf("\n");
    }*/
#endif
  /***********************/
  U_free("PLIBN_Read free error\n",&adjidx,&adjncy,&adjwgt,LEND);
  return g;
}

int PLIBN_Progen(PlotGraphType *graph, PlotGridType *grid){
  int i;
  double f, sum0, tmp;
  int totalwgt;
  
  f=0;
  for (i=0; i<grid->npro; i++){
    if (grid->proportion[i]!=0)
      f+= grid->proportion[i];
  }
  f= f/((double)grid->npro);
  sum0 = ((double)graph->nvtxs)/(((double)grid->npro)*f);

  totalwgt = graph->nvtxs;
  
  for (i=0; i<grid->npro; i++){
    tmp = (1-grid->proportion[i])*sum0;
    if (tmp !=0) 
      grid->penalty[i]=(int)floor(tmp);
    else
      grid->penalty[i] = 0;
    totalwgt += grid->penalty[i];
  }
  return totalwgt;
}

int PLIBN_RefineStats(PlotGraphType *g, PlotGridType *grid,
		      double *cutedge,double *tcc,
		      double *imbalance,double *met,double *met025,
		      double *met05,double *met1,double *met2,
		      double *proVWmin,double *proVWmax,
		      double *proVWavg,double *proVWstddev,
		      double *proVWsum,double *exec,
		      double *proETmin,
		      double *proETmax,double *proETavg,
		      double *proETstddev,double *proETsum){
  int *proVW;
  double *proET;
  
  IO_stat(TOOL_PLOT,g,grid,
	  cutedge,tcc,imbalance,met,met025,
	  met05,met1,met2,&proVW,&proET);
  U_intStat(proVW, grid->npro, proVWmin, NULL, proVWmax,
	    NULL, proVWavg,proVWstddev,proVWsum);
  U_dbStat(proET, grid->npro,proETmin, NULL, proETmax, 
	   NULL, proETavg, proETstddev,proETsum);

  memcpy(exec,proET,grid->npro*sizeof(double));

  U_free("GD_PagridRefineStats error code 3\n",&proVW,&proET,LEND);
  return 1;
}

int PLIBN_CutEdgeStats(PlotGraphType *g,double *min,double *max,double *avg,double *stddev, double* sum,PlotGridType* grid){
  int* procew;
  int* adjidx = g->adjidx;
  int* adjncy = g->adjncy;
  int* adjwgt = g->adjwgt;
  int* where  = g->pro;
  int v,w,j,jstart,jend,prov,prow,cew=0;

  WARNING((g->pro == NULL,"GD_PagridImbalance error code 1\n"),0);
  
  procew = U_mallocset(grid->npro,int,0,"PLIBN_CutEdge error code 2\n");

  for(v=0;v<g->nvtxs;v++){
    prov = where[v];
    jstart = adjidx[v];
    jend   = adjidx[v+1];

    for(j=jstart;j<jend;j++){
      w = adjncy[j];
      prow = where[w];
      if(prov != prow){
	procew[prov] += adjwgt[j];
	cew += adjwgt[j];
      }
    }
  }

  U_intStat(procew,grid->npro,min,NULL,max,NULL,avg,stddev,sum);
  *sum/=2;
  
  U_free("PLIBN_CutEdge error code 3\n",&procew,LEND);
  return 1;
}

int PLIBN_Imbalance(PlotGraphType *g,double *imb,PlotGridType *grid){
  int 
    i,
    *prowt,
    totalprowt1=0,
    totalprowt2=0,
    maxprowt1=0,
    maxprowt2=0;
  
  WARNING((g->pro == NULL,"GD_PagridImbalance error code 1\n"),0);

  prowt = U_malloc(grid->npro,int,"GD_PagridImbalance error code 2\n");
  for(i=0;i<grid->npro;i++)
    prowt[i] = 0;
  
  for(i=0;i<g->nvtxs;i++){
    prowt[g->pro[i]] += g->vwgt[i];
  }
  for(i=0;i<grid->npro;i++){
    if ((prowt[i]+grid->penalty[i])>maxprowt1)
      maxprowt1 = prowt[i]+grid->penalty[i];
    totalprowt1 += prowt[i] + grid->penalty[i];
    if ((prowt[i])>maxprowt2)
      maxprowt2 = prowt[i];
    totalprowt2 += prowt[i];
  }

  *imb = (double)maxprowt1/(double)totalprowt1*(double)grid->npro;
  /**imb = (double)maxprowt2/(double)totalprowt2*(double)grid->npro;*/
  
  U_free("GD_PagridImbalance error code 2\n",&prowt,LEND);
  return 1;
}
